#leetcode题目86：分隔链表




class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        if not data:
            return None
        
        # 创建头结点
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        
        # 逐个为 data 内的数据创建结点,建立链表
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def printlist(self, head):
        if head == None:
            return
        node = head
        while node != None:
            print(node.val, end=' ')
            node = node.next
        print()  # 换行


from typing import Optional
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left, right = ListNode(0), ListNode(0)
        l, r = left, right
        temp = head
        while temp:
            if temp.val < x:
                l.next = temp
                l = l.next
            else:
                r.next = temp
                r = r.next
            temp = temp.next
        l.next = right.next
        r.next = None
        return left.next

#测试数据
data=[1,4,3,2,5,2]
x=3
#预期输出：[1,2,2,4,3,5]
solution=Solution()
head=LinkList().initList(data)
LinkList().printlist(solution.partition(head,x))

data=[2,1]
x=2
#预期输出：[1,2]
solution=Solution()
head=LinkList().initList(data)
LinkList().printlist(solution.partition(head,x))
